#include "headfiles.h"

using namespace std;

NODE *copy_struct_recur(NODE *node, map<NODE *, NODE *> &node_map) {
    if (node == NULL) {
        return NULL;
    }

    map<NODE *, NODE *>::iterator it;
    it = node_map.find(node);
    // If the node is already copied, return what it is there
    if (it != node_map.end()) {
        return it->second;
    }

    // Otherwise, copy the node
    NODE *n;
    n = new NODE;
    if (n == NULL) {
        cout << "Allocate node structure buffer error!" << endl;
        return NULL;
    }
    node_map[node] = n;

    memcpy(n, node, sizeof(NODE));
    n->n1 = n->n2 = NULL;

    if (node->n1) {
        n->n1 = copy_struct_recur(node->n1, node_map);
    }
    
    if (node->n2) {
        n->n2 = copy_struct_recur(node->n2, node_map);
    }

    return n;
}

NODE *copy_struct(NODE *node) {
    // The map is to avoid circular in the structs
    map<NODE *, NODE *> node_map;
    return copy_struct_recur(node, node_map);
}

